#pragma once

// 这是之前没事的时候写的链表，直接拿来用了
//Based on chain, having supported all basic functions and operators except link().
#include<iostream>
#include"mybasic.h"
//The node for mychain.
template<class T>class mynode{
public:
	T shuju;
	mynode<T>* xia=nullptr;
	mynode<T>* shang=nullptr;
    mynode(){}
	void operator++(){*this=*(this->xia);}
	void operator++(int){++(*this);}
	void operator+=(int x){for(;(x--)>0;(*this)++);}
	void operator--(){*this=*(this->shang);}
	void operator--(int){--(*this);}
	void operator-=(int x){for(;(x--)>0;(*this)--);}
};
template<class T>std::istream& operator>>(std::istream &in,mynode<T> &x){return (in>>x.shuju);}
template<class T>std::ostream& operator<<(std::ostream &out,const mynode<T> &x){return (out<<x.shuju);}
template<class T>class mychain;
//The iterator for mychain.
template<class T>class mychiter:public myiter< mynode<T> >{
	friend class mychain<T>;
public:
	mychiter(){}
	virtual ~mychiter(){}
	virtual T& data(){return (this->pointer)->shuju;}
	virtual void operator++()override{this->pointer=(this->pointer)->xia;}
	virtual void operator++(int)override{++(*this);}
	virtual void operator+=(int x)override{for(;(x--)>0;(*this)++);}
	virtual void operator--()override{this->pointer=(this->pointer)->shang;}
	virtual void operator--(int)override{--(*this);}
	virtual void operator-=(int x)override{for(;(x--)>0;(*this)--);}
	virtual bool operator<=(const myiter<T> &x)const=delete;
	virtual bool operator<(const myiter<T> &x)const=delete;
	virtual bool operator>=(const myiter<T> &x)const=delete;
	virtual bool operator>(const myiter<T> &x)const=delete;
private:
	mychiter(mynode<T> *x){this->pointer=x;}
};
//template<class K,class V>class mydict;
//This chain exactly fails, as the length is fixed as a private int, making it unavailable
//for users to use iterater to erase or insert a node. Way to solving this problem can be 
//to check the length every time users need it, but this is not efficient. I keep mychain 
//here, just in preperation for the class mydict.
template<class T>class mychain{
	//template<class K,class V>friend class mydict;
private:
	mynode<T> *head=nullptr;
	mynode<T> *last=nullptr;
	int changdu=0;
	int chuli(int x)const;
	virtual mynode<T>* find(int index)const;
	virtual mynode<T>* kick(int index);
	virtual mynode<T>* kick(mynode<T>* x);
public:
	mychain(){}
	mychain(const mychain<T> &x){this->operator=(x);}
	mychain(mychain<T> &&x);
	virtual ~mychain(){this->erase();}
	virtual int length()const{return changdu;}
	virtual mychiter<T> begin(){return mychiter<T>(head);}
	virtual mychiter<T> end(){return mychiter<T>(nullptr);}
	virtual mychain& operator=(const mychain<T> &x);
	virtual mychain& operator=(mychain<T> &&x);
	virtual T& operator[](const int &x);
	virtual mychiter<T> operator()(int index)const;
	int searchforw(const T &x,const int &index=0)const;
	int searchbackw(const T &x,int index=-1)const;
	void append(const T &x);
	void append(T &&x);
	void append(const mychain<T> &x,const int &begin=0,const int &end=-1);
	void swallow(mychain<T> &x);
	void link(mychain<T> &x,int index=-1,int begin=0,int end=-1);
	void insert(const T &data,int index=0);
	void insert(const mychain<T> &x,int index=0,int begin=0,int end=-1);
	void erase(const int &begin=0,const int &end=0);
	void transto(T* const&x)const;
	void transfrom(const T* const&x,const int &len);
	void output(const char* const &gap=" ",const char* const &tail="\n",\
		std::ostream &out=std::cout)const;
	virtual bool check()const{return changdu?(head->shang==nullptr&&nullptr==last->xia):1;}
};
template<class T>int mychain<T>::chuli(int x)const{
	x%=changdu;
	return (x<0)?(x+changdu):x;
}
template<class T>mynode<T>* mychain<T>::find(int index)const{
	index=this->chuli(index);
	mynode<T>* out;
	if(2*index<changdu){
		for(out=head;(index--)>0;out=out->xia);
	}else
		for(out=last;(index++)<changdu-1;out=out->shang);
	return out;
}
template<class T>mynode<T>* mychain<T>::kick(int index){
	if(!changdu)
		return nullptr;
	index=this->chuli(index);
	mynode<T> *st=this->find(index),*st2,*st3;
	if(!(--changdu)){
		head=(last=nullptr);
	}else if(!index){
		head=st->xia;
		head->shang=nullptr;
	}else if(index==changdu){
		last=st->shang;
		last->xia=nullptr;
	}else{
		st2=st->shang;
		st3=st->xia;
		st2->xia=st3;
		st3->shang=st2;
	}
	return st;
}
template<class T>mynode<T>* mychain<T>::kick(mynode<T>* x){
	if(!changdu||x==nullptr)
		return nullptr;
	--changdu;
	mynode<T> *st=x->shang,*st2=x->xia;
	x->shang=(x->xia=nullptr);
	if(st!=nullptr)
		st->xia=st2;
	if(st2!=nullptr)
		st2->shang=st;
	return x;
}
template<class T>mychain<T>::mychain(mychain &&x){
	head=x.head;
	last=x.last;
	changdu=x.changdu;
	x.changdu=0;
	x.head=(x.last=nullptr);
}
template<class T>mychain<T>& mychain<T>::operator=(const mychain<T> &x){
	if(&x==this)return *this;
	this->erase();
	this->append(x);
	return *this;
}
template<class T>mychain<T>& mychain<T>::operator=(mychain<T> &&x){
	head=x.head;
	last=x.last;
	changdu=x.changdu;
	x.changdu=0;
	x.head=(x.last=nullptr);
	return *this;
}
template<class T>T& mychain<T>::operator[](const int &x){
	if(!changdu)
		throw "error[].";
	return find(x)->shuju;
}
template<class T>mychiter<T> mychain<T>::operator()(int index)const{
	if(!changdu)
		throw "error().";
	mychiter<T> out;
	index=this->chuli(index);
	if(2*index<changdu){
		out.pointer=head;
		out+=index;
	}else{
		out.pointer=last;
		out-=changdu-1-index;
	}
	return out;
}
template<class T>int mychain<T>::searchforw(const T &x,const int &index)const{
	if(!changdu)
		return -1;
	mynode<T> *st=this->find(index);
	int out=this->chuli(index);
	for(;out<changdu;out++){
		if(st->shuju==x)
			break;
		st=st->xia;
	}
	if(out==changdu)
		return -1;
	return out;
}
template<class T>int mychain<T>::searchbackw(const T &x,int index)const{
	if(!changdu)
		return -1;
	index=this->chuli(index);
	mynode<T> *st=this->find(index);
	for(;index>=0;--index){
		if(st->shuju==x)
			break;
		st=st->shang;
	}
	return index;
}
template<class T>void mychain<T>::append(const T &x){
	if(changdu){
		last->xia=new mynode<T>;
		last->xia->shang=last;
		last=last->xia;
	}else{
		head=new mynode<T>;
		last=head;
	}
	last->shuju=x;
	++changdu;
}
template<class T>void mychain<T>::append(T &&x){
	if(changdu){
		last->xia=new mynode<T>;
		last->xia->shang=last;
		last=last->xia;
		last->shuju=std::move(x);
	}else{
		head=new mynode<T>;
		last=head;
		head->shuju=std::move(x);
	}
	++changdu;
}
template<class T>void mychain<T>::append(const mychain<T> &x,const int &begin,const int &end){
	if(!x.changdu)
		return;
	int kaishi=x.chuli(begin),jieshu=x.chuli(end);
	if(kaishi>jieshu)
		return;
	mynode<T> *st=x.find(kaishi);
	for(;kaishi<jieshu;kaishi++){
		this->append(st->shuju);
		st=st->xia;
	}
	this->append(st->shuju);
}
template<class T>void mychain<T>::swallow(mychain<T> &x){
	if(!x.changdu)
		return;
	if(changdu){
		last->xia=x.head;
		x.head->shang=last;
	}else
		head=x.head;
	last=x.last;
	changdu+=x.changdu;
	x.changdu=0;
	x.head=nullptr;
	x.last=nullptr;
}
template<class T>void mychain<T>::link(mychain<T> &x,int index,int begin,int end){
	throw "haven't finished function link.";
	if(!x.changdu)
		return;
	int kaishi=x->chuli(begin),jieshu=x->chuli(end);
	if(kaishi>jieshu)
		return;
	mynode<T> *xst1=x->find(kaishi),*xst2=x->find(jieshu),*st[4];
	if(!changdu){
		if(!kaishi){
			changdu=jieshu+1-kaishi;
			x.head=xst2->xia;
			if(jieshu!=x.changdu-1)
				x.head->shang=nullptr;
			x.changdu-=jieshu+1-kaishi;
			head=xst1;
			last=xst2;
			last->xia=nullptr;
			return;
		}
	}
	int shiji=this->chuli(index);
	mynode<T> *sst=this->find(shiji);
	
}
template<class T>void mychain<T>::insert(const T &data,int index){
	if(!changdu){
		this->append(data);
		return;
	}
	index=this->chuli(index);
	if(!index){
		mynode<T> *cun=head;
		head=new mynode<T>;
		head->shuju=data;
		head->xia=cun;
		cun->shang=head;
		++changdu;
		return;
	}
	mynode<T> *st=this->find(index),*st2,*st3;
	st2=st;
	st3=st->shang;
	st=new mynode<T>;
	st->shang=st3;
	st2->shang=st;
	st->shuju=data;
	st->xia=st2;
	st3->xia=st;
	++changdu;
}
template<class T>void mychain<T>::insert(const mychain<T> &x,int index,int begin,int end){
	if(!x.changdu)
		return;
	if(!changdu){
		this->append(x,begin,end);
		return;
	}
	begin=x.chuli(begin),end=x.chuli(end),index=this->chuli(index);
	mynode<T> *st=x.find(end),*sst,*sst2,*sst3;
	if(!index){
		changdu+=end+1-begin;
		for(;begin<=end;begin++){
			sst2=head;
			head=new mynode<T>;
			head->shuju=st->shuju;
			head->xia=sst2;
			sst2->shang=head;
			if(begin!=end)
				st=st->shang;
		}
		return;
	}
	sst=this->find(index);
	changdu+=end+1-begin;
	for(;begin<=end;begin++){
		sst2=sst;
		sst3=sst->shang;
		sst=new mynode<T>;
		sst->shang=sst2->shang;
		sst2->shang=sst;
		sst->shuju=st->shuju;
		sst->xia=sst2;
		sst3->xia=sst;
		st=st->shang;
	}
}
template<class T>void mychain<T>::erase(const int &begin,const int &end){
	if(!changdu)
		return;
	int kaishi=this->chuli(begin),jieshu=this->chuli(end-1);
	if(kaishi>jieshu)
		return;
	jieshu++;
	mynode<T> *jilu=nullptr,*st=nullptr,*jilu2=nullptr;
	if(kaishi<=changdu-jieshu){
		jilu=head;
		for(int i=0;i<kaishi;i++)
			jilu=jilu->xia;
		if(jilu!=head){
			jilu2=jilu->shang;
			jilu2->xia=nullptr;
		}
		for(int i=kaishi;i<jieshu;i++){
			st=jilu->xia;
			if(jilu!=last)
				st->shang=nullptr;
			delete jilu;
			jilu=st;
		}
		if(jilu2!=nullptr)
			jilu2->xia=jilu;
		else
			head=jilu;
		if(changdu-jieshu+kaishi)
			jilu->shang=jilu2;
	}else{
		jilu=last;
		for(int i=0;i<changdu-jieshu;i++)
			jilu=jilu->shang;
		if(jilu!=last){
			jilu2=jilu->xia;
			jilu2->shang=nullptr;
		}
		for(int i=kaishi;i<jieshu;i++){
			st=jilu->shang;
			delete jilu;
			st->xia=nullptr;
			jilu=st;
		}
		if(jilu2!=nullptr)
			jilu2->shang=jilu;
		else
			last=jilu;
		if(changdu-jieshu+kaishi)
			jilu->xia=jilu2;
	}
	changdu-=jieshu-kaishi;
	if(!changdu){
		head=nullptr;
		last=nullptr;
	}
}
template<class T>
void mychain<T>::transto(T* const&x)const{
	mynode<T> *st=head;
	for(int i=0;i<changdu;i++){
		x[i]=st->shuju;
		st=st->xia;
	}
}
template<class T>
void mychain<T>::transfrom(const T* const&x,const int &len){
	this->erase();
	for(int i=0;i<len;i++)
		this->insert(x[i]);
}
template<class T>
void mychain<T>::output(const char* const &gap,const char* const &tail,\
std::ostream &out)const{
	mynode<T> *st=head;
	for(int i=0;i<changdu-1;i++){
		out<<st->shuju<<gap;
		st=st->xia;
	}
	if(changdu)
		out<<st->shuju;
	out<<tail;
}
template<class T>
std::ostream& operator<<(std::ostream &out,const mychain<T> &x){
	x.output(" ","",out);
	return out;
}
